package LinkList;

import org.junit.Test;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: LinkList
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-23  23:07
 * @Description: TODO
 * @Version: 1.0
 */
public class 旋转链表61 {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode reverseBetween3(ListNode head, int left, int right) {
        if (head == null) {
            return head;
        }
        ListNode dumpy = new ListNode(-1);
        dumpy.next = head;

        ListNode pre = dumpy;
        // 遍历到left的前面一个位置
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode curr = pre.next;
        for (int i = 0; i < right - left; i++) {
            ListNode future = curr.next;
            curr.next = future.next;
            future.next = pre.next;
            pre.next = future;
        }
        return dumpy.next;
    }

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        int count = 0;
        ListNode curr = head;
        while (curr != null) {
            count++;
            curr = curr.next;
        }
        k = k % count;
        System.out.println("count=" + count);
        ListNode node1 = reverseBetween3(head, 1, count - k);
        ListNode node2 = reverseBetween3(node1, count - k + 1, count);
        ListNode node3 = reverseBetween3(node2, 1, count);
        return node3;
    }

    public ListNode rotateRight2(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        int n = 1;
        ListNode iter = head;
        while (iter.next != null) {
            iter = iter.next;
            n++;
        }
        int add = n - k % n;
        if (add == n) {
            return head;
        }
        // 构建成为一个圆环
        iter.next = head;
        // 遍历add 次
        while (add-- > 0) {
            iter = iter.next;
        }
        // 设置新的节点
        ListNode ret = iter.next;
        // 切开
        iter.next = null;
        return ret;
    }


    @Test
    public void test() {
        ListNode s1 = new ListNode(1);
        ListNode s2 = new ListNode(2);
        ListNode s3 = new ListNode(3);
        ListNode s4 = new ListNode(4);
        ListNode s5 = new ListNode(5);

        s1.next = s2;
        s2.next = s3;
        s3.next = s4;
        s4.next = s5;
        ListNode listNode = rotateRight(s1, 2);
        ListNode curr = listNode;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }

    }


}
